package leetcode.code0794;

import java.util.HashSet;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/***
 * 仅做源头管理的并查集 执行用时：19 ms, 在所有 Java 提交中击败了14.55%的用户
 *
 * 内存消耗：41.2 MB, 在所有 Java 提交中击败了5.45%的用户
 *
 * 通过测试用例：32 / 32
 *
 * 相对于2，增加移除传染源，效果不大。
 ***/
public class Solution22 implements IDebug {

	int[][] isInfected;
	int m, n;
	int[] d = new int[] { 0, 1, 0, -1, -1, 0, 1, 0 };

	class Union {
		// 传统并查集
		int[] represent;
		int[] sizes;

		int[] stack;
		int pstack;

		// 感染源头
		Set<Integer> infectSource;

		// 测试用
		int groupSize;

		public Union() {
			int len = m * n;
			this.represent = new int[len];
			this.sizes = new int[len];
			this.stack = new int[len];
			this.pstack = 0;
			this.infectSource = new HashSet<>();
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					int index = this.index(i, j);
					this.represent[index] = index;
					this.sizes[index] = 1;
					if (isInfected[i][j] == 1) {
						this.infectSource.add(index);
					}
				}
			}
			this.groupSize = len;
			this.initUnion();

		}

		private int index(int x, int y) {
			return x * n + y;
		}

		private void initUnion() {
			int last = isInfected[0][0];
			for (int i = 1; i < m; i++) {
				int cur = isInfected[i][0];
				if (cur == 1 && last == 1) {
					this.join(i - 1, 0, i, 0);
				}
				last = cur;
			}
			last = isInfected[0][0];
			for (int i = 1; i < n; i++) {
				int cur = isInfected[0][i];
				if (cur == 1 && last == 1) {
					this.join(0, i - 1, 0, i);
				}
				last = cur;
			}
			for (int i = 1; i < m; i++) {
				for (int j = 1; j < n; j++) {
					int cur = isInfected[i][j];
					if (cur == 1) {
						if (isInfected[i - 1][j] == 1) {
							this.join(i - 1, j, i, j);
						}
						if (isInfected[i][j - 1] == 1) {
							this.join(i, j - 1, i, j);
						}
					}
				}
			}
		}

		private void join(int x1, int y1, int x2, int y2) {
			int r1 = this.represent(this.index(x1, y1));
			int r2 = this.represent(this.index(x2, y2));
			if (r1 != r2) {
				int size1 = this.sizes[r1];
				int size2 = this.sizes[r2];
				if (size1 < size2) {
					this.represent[r1] = r2;
					this.sizes[r2] = size1 + size2;
					this.infectSource.remove(r1);
				} else {
					this.represent[r2] = r1;
					this.sizes[r1] = size1 + size2;
					this.infectSource.remove(r2);
				}
				this.groupSize--;
			}
		}

		private int represent(int index) {
			this.pstack = 0;
			int ans = 0;
			while ((ans = this.represent[index]) != index) {
				this.stack[this.pstack++] = index;
				index = ans;
			}
			while (this.pstack > 0) {
				this.represent[this.stack[--this.pstack]] = ans;
			}
			return ans;
		}

	}

	Union union;

	public int containVirus(int[][] isInfected) {
		this.isInfected = isInfected;
		this.m = isInfected.length;
		this.n = isInfected[0].length;
		int ans = 0;
		int wall = 0;
		union = new Union();
		do {
			if (wall != 0) {
				this.infect();
			}
			int[] cur = this.maxWall();
			wall = cur[0];
			union.infectSource.remove(cur[1]);
			ans += wall;
		} while (wall != 0);
		return ans;
	}

	private int[] maxWall() {
		boolean[][] flag = new boolean[m][n];
		int maxm = -1, maxn = -1, wall = 0, refer = 0;
		int maxIndex = 0;
		for (Integer index : union.infectSource) {
			int i = index / n, j = index % n;
			boolean[][] refers = new boolean[m][n];
			int[] count = this.countWall(i, j, flag, refers);
			if (count[1] > refer) {
				refer = count[1];
				wall = count[0];
				maxm = i;
				maxn = j;
				maxIndex = index;
			}
		}
		if (maxm != -1) {
			this.isolation(maxm, maxn);
		}
		return new int[] { wall, maxIndex };
	}

	private void isolation(int x, int y) {
		this.isInfected[x][y] = 2;
		for (int i = 0; i < 8; i += 2) {
			int nextx = x + d[i], nexty = y + d[i + 1];
			if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && this.isInfected[nextx][nexty] == 1) {
				this.isolation(nextx, nexty);
			}
		}
	}

	private int[] countWall(int x, int y, boolean[][] flag, boolean[][] refers) {
		int[] ans = new int[] { 0, 0 };
		if (flag[x][y] || this.isInfected[x][y] != 1) {
			return ans;
		}
		flag[x][y] = true;
		for (int i = 0; i < 8; i += 2) {
			int nextx = x + d[i], nexty = y + d[i + 1];
			if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
				int next = this.isInfected[nextx][nexty];
				if (next == 0) {
					ans[0] += 1;
					if (!refers[nextx][nexty]) {
						refers[nextx][nexty] = true;
						ans[1] += 1;
					}
				} else if (next == 1) {
					int[] nextCount = this.countWall(nextx, nexty, flag, refers);
					ans[0] += nextCount[0];
					ans[1] += nextCount[1];
				}
			}
		}
		return ans;
	}

	private void infect() {
		boolean[][] flag = new boolean[m][n];
		for (Integer index : union.infectSource) {
			int i = index / n, j = index % n;
			this.spread(i, j, flag);
		}
	}

	private void spread(int x, int y, boolean[][] flag) {
		if (this.isInfected[x][y] != 1 || flag[x][y]) {
			return;
		}
		flag[x][y] = true;
		for (int i = 0; i < 8; i += 2) {
			int nextx = x + d[i], nexty = y + d[i + 1];
			if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
				int next = this.isInfected[nextx][nexty];
				if (next == 0) {
					flag[nextx][nexty] = true;
					this.isInfected[nextx][nexty] = 1;
				} else {
					this.spread(nextx, nexty, flag);
				}
			}
		}
	}

	@Override
	public void debug1() {
		HelpDebug.compare(10, this.containVirus(
				HelpDebug.str2array1("[[0,1,0,0,0,0,0,1],[0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0]]")));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
		HelpDebug.compare(4, this.containVirus(HelpDebug.str2array1("[[1,1,1],[1,0,1],[1,1,1]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		HelpDebug.compare(13, this.containVirus(HelpDebug.str2array1("[[1,1,1,0,0,0,0,0,0],[1,0,1,0,1,1,1,1,1],[1,1,1,0,0,0,0,0,0]]")));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

		HelpDebug.compare(38, this.containVirus(HelpDebug.str2array1(
				"[[0,1,0,1,1,1,1,1,1,0],[0,0,0,1,0,0,0,0,0,0],[0,0,1,1,1,0,0,0,1,0],[0,0,0,1,1,0,0,1,1,0],[0,1,0,0,1,0,1,1,0,1],[0,0,0,1,0,1,0,1,1,1],[0,1,0,0,1,0,0,1,1,0],[0,1,0,1,0,0,0,1,1,0],[0,1,1,0,0,1,1,0,0,1],[1,0,1,1,0,1,0,1,0,1]]")));
	}

	public static void main(String[] args) {
		Solution22 so = new Solution22();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
